from typing import Dict, List, Optional

class Tree:
    @staticmethod
    def get_tree_child(target_id: int, data: Dict[int, Dict]) -> str:
        """获取指定分类的所有子类ID（包含自身）"""
        subs = {target_id}
        processed = set()
        data_copy = data.copy()  # 避免修改原始数据
        
        while True:
            prev_len = len(subs)
            to_add = set()
            
            for cate_id, item in list(data_copy.items()):
                if item['followid'] in subs and cate_id not in subs:
                    to_add.add(cate_id)
                    del data_copy[cate_id]  # 模拟PHP的unset优化
            
            subs.update(to_add)
            if len(subs) == prev_len:
                break
        
        return ','.join(map(str, sorted(subs)))

    @staticmethod
    def get_tree_parent(target_id: int, data: Dict[int, Dict]) -> List[int]:
        """获取指定分类的父类路径（从根到当前）"""
        path = []
        current_id = target_id
        
        while current_id != 0:
            if current_id not in data:
                break
            path.append(current_id)
            current_id = data[current_id]['followid']
        
        return list(reversed(path))

    @staticmethod
    def get_tree(data: Dict[int, Dict]) -> Dict[int, Dict]:
        """增强树形结构数据（添加父子关系信息）"""
        enhanced = {}
        
        for cate_id, item in data.items():
            parent_path = Tree.get_tree_parent(cate_id, data)
            son_ids = Tree.get_tree_child(cate_id, data)
            
            enhanced[cate_id] = {
                **item,
                'parent': ','.join(map(str, parent_path)),
                'sonid': son_ids,
                'child': len(son_ids.split(',')) - 1
            }
        
        return enhanced

    @staticmethod
    def get_trees(data: Dict[int, Dict], root_id: int) -> List[Dict]:
        """生成树形结构列表（带深度信息）"""
        stack = [root_id]
        child_map: Dict[int, Optional[List[int]]] = {}
        obj_map: Dict[int, Dict] = {}
        result = []
        added = set()
        depth = -1
        
        # 构建子节点映射
        for cate_id, node in data.items():
            pid = node['followid']
            if pid not in child_map:
                child_map[pid] = []
            child_map[pid].append(cate_id)
            obj_map[cate_id] = node
        
        loop_count = 0
        while stack:
            current_id = stack[0]
            node = obj_map.get(current_id)
            has_child = False
            
            # 处理子节点
            if child_map.get(current_id):
                has_child = True
                # 反向添加子节点到栈顶
                for child_id in reversed(child_map[current_id]):
                    if child_id in obj_map:
                        stack.insert(0, child_id)
            
            # 添加当前节点到结果
            if current_id != root_id and node and current_id not in added:
                added.add(current_id)
                result.append({**node, 'depth': depth})
            
            # 深度调整
            if has_child:
                depth += 1
            else:
                # 回溯处理
                if node:
                    parent_id = node['followid']
                    if parent_id in child_map and child_map[parent_id]:
                        try:
                            child_map[parent_id].remove(current_id)
                        except ValueError:
                            pass
                        
                        if not child_map[parent_id]:
                            child_map[parent_id] = None
                            depth -= 1
                
                stack.pop(0)
            
            # 防止死循环
            loop_count += 1
            if loop_count > 5000:
                break
        
        return result

"""
使用方法示例：
# 准备测试数据（格式：{cateid: {cateid, followid, ...}}）
test_data = {
    1: {'cateid': 1, 'followid': 0, 'name': 'Root'},
    2: {'cateid': 2, 'followid': 1, 'name': 'Child1'},
    3: {'cateid': 3, 'followid': 1, 'name': 'Child2'},
    4: {'cateid': 4, 'followid': 2, 'name': 'Grandchild'}
}

# 获取完整树结构
full_tree = Tree.get_tree(test_data)

# 获取子节点
print(Tree.get_tree_child(2, test_data))  # 输出 "2,4"

# 获取父路径
print(Tree.get_tree_parent(4, test_data))  # 输出 [1, 2, 4]

# 生成带深度的树列表
tree_list = Tree.get_trees(test_data, 1)
for node in tree_list:
    print(f"Depth {node['depth']}: {node['name']}")

输出结果：
Depth 0: Child1
Depth 1: Grandchild
Depth 0: Child2
"""